In order to take sharper pictures of a scene, a digital camera may be equipped with a moveable lens system that is controlled by an automatic lens focusing system or autofocus system. When the user has pressed the camera's shutter button part way, the autofocus system responds by quickly calculating the correct lens position that results in a subject in the scene being in focus, before the user has pressed the shutter button all the way (at which point a final picture of the scene is taken or accepted and then stored in the camera). Obtaining the correct focus quickly is important in digital cameras running on battery power because time and power usage should be minimized to the extent possible. The autofocus system should also work in a continuous image capture mode where the camera takes a rapid sequence of still pictures (e.g., video). For instance, in a video mode the focus is automatically adjusted in real-time as the scene changes.
The hill-dimb algorithm is often used in autofocus systems. The algorithm determines a focus state of the moveable lens system for a given scene, through digital image analysis of a series of images that are captured with the moveable lens system configured at different lens focus distances or positions. A focus value is calculated for each image in the sequence. The goal is to generate a sequence of focus values that increase in level until they pass over a peak, i.e. a “hill”, which represents the best focus value for the given scene. For example, the lens focus position is adjusted automatically until certain edge detail in the image is maximized. The algorithm is shown in the diagram of FIG. 1, which illustrates the relationship between a focus sharpness and lens position according to the prior art. In FIG. 1, the abscissa indicates the focusing position of a lens along a distance axis, the ordinate indicates the focusing evaluation value (i.e., sharpness), and the curves A and B indicate the focusing evaluation values for high and low frequency components, respectively, relative to a particular in-focus position P. In order to decrease focusing response time without sacrificing focusing precision, a lens may be quickly driven in coarse adjustment steps in a low frequency range furthest from the maximum focus, and then driven in finer adjustment steps in a high frequency range nearer to the maximum focus. Once the peak of the hill is passed (curve B in FIG. 1), a high frequency bandpass filter is loaded, and the lens is moved in the opposite direction until the peak of the higher hill is found (curve A in FIG. 1). The peak focus value may use either the weighted average or peak value from numerous pixels.
Autofocus systems using the hill-climb algorithm are typically accurate in that they lead to relatively sharp pictures. Unfortunately, such autofocus systems can be relatively slow in determining a focus setting due to the large number of autofocus images that must be captured and compared. For example, an autofocus system using the hill-dimb algorithm can take up to nine (9) frames to calculate the lens focus position taking as long as 0.5 seconds to 2.0 seconds to determine focus conditions. Autofocus algorithms such as the hill-climb algorithm in general also suffer in a low-light environment since the autofocus has difficulty capturing enough edge information to properly focus.